package leetcode;

/**
 * Created by Ghost on 2015/1/28 0028.
 */


/**
 * 需要一个DP解法
 */
public class Interleaving_String {//递归
    public boolean search(char[] c, int current, char[] a, int A, char[] b, int B, boolean upLevel) {
        if (!upLevel)
            return false;
        else {
            if (current == c.length) {
                return true;
            } else {
                boolean rst1 = false, rst2 = false;
                if (A < a.length && c[current] == a[A]) {
                    rst1 = search(c, current + 1, a, A + 1, b, B, true);
                }
                if (B < b.length && c[current] == b[B])
                    rst2 = search(c, current + 1, a, A, b, B + 1, true);
                return (rst1 || rst2);
            }
        }
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3 == null || s3.length() == 0)
            return false;
        if (s1 == null || s1.length() == 0)
            return s3.equals(s2);
        if (s2 == null || s2.length() == 0)
            return s3.equals(s1);
        char[] a = s1.toCharArray();
        char[] b = s2.toCharArray();
        char[] c = s3.toCharArray();

        return search(c, 0, a, 0, b, 0, true);
    }

    public static void main(String[] args) {
        Interleaving_String interleaving_string = new Interleaving_String();
        System.out.println(interleaving_string.isInterleave("", "", ""));
    }
}
